package arithmetic.someAlgorithm;

/**
 * 找一个乱序数组中的中位数
 * @author lidd
 *
 */
public class MiddleNum {

	public static void main(String[] args) {

		int [] arr = new int[] {2,4,9,5,7,8,3,1,6,10};
		int middle = findMiddle(arr,0,arr.length-1);
		System.out.println(middle);
	}

	public static int findMiddle(int arr[], int _left, int _right) {
		int left = _left;
		int right = _right;
		int mid = (0+arr.length-1)/2;
		int temp = 0;
		if (left <= right) { // 待排序的元素至少有两个的情况
			temp = arr[left]; // 待排序的第一个元素作为基准元素
			while (left != right) { // 从左右两边交替扫描，直到left = right

				while (right > left && arr[right] >= temp)
					right--; // 从右往左扫描，找到第一个比基准元素小的元素
				arr[left] = arr[right]; // 找到这种元素arr[right]后与arr[left]交换

				while (left < right && arr[left] <= temp)
					left++; // 从左往右扫描，找到第一个比基准元素大的元素
				arr[right] = arr[left]; // 找到这种元素arr[left]后，与arr[right]交换

			}
			arr[right] = temp; // 基准元素归位
			if(right == mid) {
				return arr[mid];
			}else if(right > mid) {
				return findMiddle(arr, _left, left - 1); // 对基准元素左边的元素进行递归排序
			}else if(right < mid) {
				return findMiddle(arr, right + 1, _right); // 对基准元素右边的进行递归排序
			}
		}
		return -1;
	}
}
